package utils

/**
德洛内(Delaunay)三角网
*/

import (
	"math"
)

type DelaunayEdge struct {
	V1, V2 DelaunayVertex
	isBad  bool
}

//type DelaunayVertex struct {
//	X, Y float64
//}

type DelaunayVertex PointXy

func (this *DelaunayVertex) Same(v *DelaunayVertex) bool {
	return this.X == v.X && this.Y == v.Y
}

type DelaunayTriangle struct {
	P1, P2, P3 DelaunayVertex
	E1, E2, E3 DelaunayEdge
	isBad      bool
}

func Max(x, y float64) float64 {
	if x >= y {
		return x
	} else {
		return y
	}
}

func (this *DelaunayTriangle) ContiansPoint(x, y float64) bool {
	var p0 PointXy
	p0.X, p0.Y = x, y
	return TriangleContainByRay(PointXy(this.P1), PointXy(this.P2), PointXy(this.P3), p0)
}

func (this *DelaunayTriangle) containsVertex(v DelaunayVertex) bool {
	return this.P1 == v || this.P2 == v || this.P3 == v
}

func (this *DelaunayTriangle) CircumCircleContains(v DelaunayVertex) bool {
	ab := (this.P1.X * this.P1.X) + (this.P1.Y * this.P1.Y)
	cd := (this.P2.X * this.P2.X) + (this.P2.Y * this.P2.Y)
	ef := (this.P3.X * this.P3.X) + (this.P3.Y * this.P3.Y)

	circum_x := (ab*(this.P3.Y-this.P2.Y) + cd*(this.P1.Y-this.P3.Y) + ef*(this.P2.Y-this.P1.Y)) / (this.P1.X*(this.P3.Y-this.P2.Y) + this.P2.X*(this.P1.Y-this.P3.Y) + this.P3.X*(this.P2.Y-this.P1.Y)) / 2.0
	circum_y := (ab*(this.P3.X-this.P2.X) + cd*(this.P1.X-this.P3.X) + ef*(this.P2.X-this.P1.X)) / (this.P1.Y*(this.P3.X-this.P2.X) + this.P2.Y*(this.P1.X-this.P3.X) + this.P3.Y*(this.P2.X-this.P1.X)) / 2.0
	circum_radius := math.Sqrt(
		((this.P1.X - circum_x) * (this.P1.X - circum_x)) + ((this.P1.Y - circum_y) * (this.P1.Y - circum_y)))

	dist := math.Sqrt(
		((v.X - circum_x) * (v.X - circum_x)) + ((v.Y - circum_y) * (v.Y - circum_y)))
	return dist <= circum_radius
}

func CalcuTriangulate(vertices []DelaunayVertex) ([]DelaunayTriangle, []DelaunayEdge) {
	//_vertices:= vertices
	minX := vertices[0].X
	minY := vertices[0].Y
	maxX := minX
	maxY := minY

	trianglelst := make([]DelaunayTriangle, 0, 10)
	for i := 0; i < len(vertices); i++ {
		if vertices[i].X < minX {
			minX = vertices[i].X
		}
		if vertices[i].Y < minY {
			minY = vertices[i].Y
		}
		if vertices[i].X > maxX {
			maxX = vertices[i].X
		}
		if vertices[i].Y > maxY {
			maxY = vertices[i].Y
		}
	}

	dx := maxX - minX
	dy := maxY - minY
	deltaMax := Max(float64(dx), float64(dy))
	midx := (minX + maxX) / 2.0
	midy := (minY + maxY) / 2.0

	var p1, p2, p3 DelaunayVertex
	p1.X = midx - 20*deltaMax
	p1.Y = midy - deltaMax
	p2.X = midx
	p2.Y = midy + 20*deltaMax
	p3.X = midx + 20*deltaMax
	p3.Y = midy - deltaMax

	var t DelaunayTriangle
	t.P1 = p1
	t.P2 = p2
	t.P3 = p3
	t.isBad = false

	t.E1.V1.X = p1.X
	t.E1.V1.Y = p1.Y
	t.E1.V2.X = p2.X
	t.E1.V2.Y = p2.Y
	t.E1.isBad = false

	t.E2.V1.X = p2.X
	t.E2.V1.Y = p2.Y
	t.E2.V2.X = p3.X
	t.E2.V2.Y = p3.Y
	t.E2.isBad = false

	t.E3.V1.X = p3.X
	t.E3.V1.Y = p3.Y
	t.E3.V2.X = p1.X
	t.E3.V2.Y = p1.Y
	t.E3.isBad = false

	trianglelst = append(trianglelst, t)
	for i := 0; i < len(vertices); i++ {
		polygon := make([]DelaunayEdge, 0, 10)
		for k := 0; k < len(trianglelst); k++ {
			if trianglelst[k].CircumCircleContains(vertices[i]) {
				trianglelst[k].isBad = true
				polygon = append(polygon, trianglelst[k].E1)
				polygon = append(polygon, trianglelst[k].E2)
				polygon = append(polygon, trianglelst[k].E3)
			} else {
				//fmt.Println(" does not contains  in his circum center" )
			}
		}
		trianglelst = removeBadTriangle(trianglelst)

		for i := 0; i < len(polygon); i++ {
			for k := 0; k < len(polygon); k++ {
				if polygon[i] == polygon[k] {
					continue
				}
				if ((polygon[i].V1 == polygon[k].V1 && polygon[i].V2 == polygon[k].V2) ||
					(polygon[i].V1 == polygon[k].V2 && polygon[i].V2 == polygon[k].V1)) &&
					(polygon[i].isBad == polygon[k].isBad) {
					polygon[i].isBad = true
					polygon[k].isBad = true
				}
			}
		}

		polygon = removeBadEdges(polygon)

		for p := 0; p < len(polygon); p++ {
			var t DelaunayTriangle

			t.P1 = polygon[p].V1
			t.P2 = polygon[p].V2
			t.P3 = vertices[i]
			t.isBad = false

			t.E1.V1.X = polygon[p].V1.X
			t.E1.V1.Y = polygon[p].V1.Y
			t.E1.V2.X = polygon[p].V2.X
			t.E1.V2.Y = polygon[p].V2.Y
			t.E1.isBad = false

			t.E2.V1.X = polygon[p].V2.X
			t.E2.V1.Y = polygon[p].V2.Y
			t.E2.V2.X = vertices[i].X
			t.E2.V2.Y = vertices[i].Y
			t.E2.isBad = false

			t.E3.V1.X = vertices[i].X
			t.E3.V1.Y = vertices[i].Y
			t.E3.V2.X = polygon[p].V1.X
			t.E3.V2.Y = polygon[p].V1.Y
			t.E3.isBad = false

			trianglelst = append(trianglelst, t)
		}
	}

	trianglelst = removeTriangles(trianglelst, p1, p2, p3)
	edges := make([]DelaunayEdge, 0, 10)
	for i := 0; i < len(trianglelst); i++ {
		edges = append(edges, trianglelst[i].E1)
		edges = append(edges, trianglelst[i].E2)
		edges = append(edges, trianglelst[i].E3)
	}

	//var E1,E2 int=0,0
	for i := 0; i < len(edges); i++ {
		for k := i; k < len(edges); k++ {
			if i == k {
				continue
			}
			if ((edges[i].V1 == edges[k].V1 && edges[i].V2 == edges[k].V2) ||
				(edges[i].V1 == edges[k].V2 && edges[i].V2 == edges[k].V1)) &&
				edges[i].isBad == edges[k].isBad {
				edges[i].isBad = true
			}
		}
	}
	edges = removeBadEdges(edges)
	return trianglelst, edges
}

func removeBadEdges(this []DelaunayEdge) []DelaunayEdge {
	for i := 0; i < len(this); i++ {
		if this[i].isBad {
			this = append(this[:i], this[i+1:]...)
			i--
		}
	}
	return this

}
func removeBadTriangle(this []DelaunayTriangle) []DelaunayTriangle {
	for i := 0; i < len(this); i++ {
		if this[i].isBad {
			this = append(this[:i], this[i+1:]...)
			i--
		}
	}
	return this
}

/*
移除包含有p1,p2,p3的三角形
*/
func removeTriangles(this []DelaunayTriangle, p1, p2, p3 DelaunayVertex) []DelaunayTriangle {
	for i := 0; i < len(this); i++ {
		if this[i].containsVertex(p1) || this[i].containsVertex(p2) || this[i].containsVertex(p3) {
			this = append(this[:i], this[i+1:]...)
			i--
		}
	}
	return this
}
